本校同學希望旁聽課程請直接聯絡助教吳政宏 r11921036@ntu.edu.tw

In this course, we will study various techniques for designing and analyzing algorithms. We will mainly focus on problems for which the exact algorithm is not known or not efficient enough and problems with resource constraints. Besides designing efficient algorithms, proving the performance guarantees is also a main topic of this course.

In the first half of the semester, we will focus on approximation algorithms. Approximation algorithms are algorithms that find near-optimal solutions with provable performance guarantees in polynomial time. We will cover design techniques such as rounding and primal-dual algorithms.

In the second half of the semester, we will focus on different topics in randomized algorithms. We will cover algorithm design techniques such as hashing, sampling, random walks, and derandomization.